COMMENT ⊗   VALID 00013 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.device xgp
C00004 00003	.every heading()
C00006 00004	.s Summary
C00009 00005	.s Goals
C00016 00006	.app New Personnel
C00020 00007	.app Text of December 1977 Proposal
C00024 00008	.s Work Plan
C00028 00009	.ss Crossbar Switch Design
C00033 00010	.s Coordination and Reporting
C00036 00011	.app SAIL Background in System Development
C00044 00012	.bib
C00047 00013	.next page app Budget
C00066 ENDMK
C⊗;
.device xgp
.if xcribl then start "xgp"
.require "bask.pub[sub,sys]" source_file;
.font 5 "metlb"; font 6 "metmb";
.font 7 "gacl25";
. end "xgp";
.sides←1;
.require "twocol.pub[sub,sys]" source_file;
.macro sskip	⊂skip(if lines<15 then 200 else 2)⊃;	<< section skip control >>
.macro appskip	⊂skip 200⊃;		<< appendix skip >>
.if ¬xcribl then start "tty"
.    page frame 52 high 72 wide;
.    title area heading lines 1 to 3
.    area text lines 4 to 52;
.    end "tty";
.
.MACRO BC ⊂ BEGIN PREFACE 0; INDENT 1,4; CRBREAK nojust ⊃
.
.MACRO BS ⊂ BEGIN PREFACE 0; INDENT 1,4; nojust ⊃
.
.MACRO IB ⊂ turn on "%";
.AT """" ⊂ (IF THISFONT=1 THEN "%3" ELSE "%1"); ⊃
.AT "<" ⊂ "%2" ⊃;  AT ">" ⊂ "%1" ⊃;
. ⊃

.MACRO BIB  ⊂  CB(References);
.	BEGIN INDENT 0,3; NOJUST; IB;
.	AT "AIM-" ⊂ "Stanford AI Memo AαIαMα-" ⊃;
.	COUNT exref TO 200
.	AT "⊗" ⊂ IF LINES<3 THEN NEXT COLUMN; NEXT EXREF; ("["&EXREF&"]  ") ⊃
.	⊃
.SECNAME←"";
.portion some; place text;
.every heading();
.onecol;
.begin "cover"
.center; select 6;
November 1978




Proposal to

%5University of California
Lawrence Livermore Laboratory%6

for design of

%5An Operating System for the S-1 Computer%6
.skip 2
John McCarthy, Professor of Computer Science
Forest Baskett, Associate Professor of Computer Science
Co-principal Investigators
.skip 10;
Abstract
.skip
.begin fill;
The Stanford Artificial Intelligence Laboratory proposes to continue
participation in the Lawrence Livermore Laboratory program for development
of the S-1 computer system.
This proposal covers a one-year period beginning 1 January 1979.
.end
.skip 10
%5Computer Science Department
Stanford University
.end "cover"
.every heading(,"S-1 Proposal",{page});
.count page;
.if xcribl then twocol;
.s Summary
The Stanford Artificial Intelligence Laboratory proposes to continue
development work on the S1 computer system, as planned in our proposal of
December 1977 (Appendix B).
This proposal covers calendar year 1979.

In the period April 1978 to the present, the following has been accomplished.
.begin indent 4,7; nojust
1.  Preliminary design of operating system.

2.  Support programs have been developed as follows:
.begin preface 0; indent 7,10;crbreak
a.  S1 simulator,
b.  Cross-assembler for S1 code running on PDP-10,
c.  S1 debugger,
d.  PDP-10 simulator for S1,
e.  AN UYK-7 simulator,
f.  Memory diagnostic
.end

3.  A set of numerical rountines has been written for the S1
(SQRT, SIN, COS, ATAN, LOG, EXP).

4.  Detailed design and layout of the memory switch is well underway.
At this writing,
all data paths and about 90α% of the control logic have been designed.
Diagnostic hardware design is just beginning and physical layout
is yet to be done.

5.  Assistance has been provided in other hardware design, mainly the
memory interface for the Mark I processor.
.end

Professor Forest Baskett has joined the project as Co-principal Investigator
and will coordinate system programming efforts.  Professor John Hennessy
has also joined in this effort.  See Appendix A for more on their interests.
.s Goals

The main thrust of the proposed extension is two part: to develop
suitable language designs and processors to be used 
to write the S-1 operating system, and to investigate 
the specification of the operating system kernel.

The major components of this project are:

1) Complete the design of an extended version 
of the Pascal language to support the systems programming effort.
Continue to respond to new situations which occur in the actual 
construction of the operating system.

2) Implement the extended language using exisiting compilers
as a basis. 

3) Upgrade the exisiting Pascal compilers to 
be fully compatable with standard Pascal. This
is also required to support the optimizer under construction
by Dick Sites.

4) Upgrade the P-code to S-1 Translator
(SOPA) to support full and extended Pascal. Changes are also necessary
to conform to new schemes being used in the code generator.

5) Implement intermodule type checking, so that Pascal
and extended Pascal programs can be separately compiled by modules.
This will involve either upgrading the current linker or inserting
a prelinker pass to check type compatability.

6) Investigate the design of a kernel for the
S-1 operating system. This effort will concentrate on specifying
a minimal kernel to support operating system functions.


.s Work Plan
.ss Programming Language Development

The programming language design work will go on largely in parallel.
The first step of specifying the Extended Pascal has been 
partially completed (the specification appears in the Appendix).
Implementation of this design is expected to start very shortly.
A preliminary version of the Extended Language will be
available by July 1, 1979, and the final version of the compiler
will be delivered by September 30, 1979. 
The upgrade of the language processors for Pascal will occur
in parallel with the new language implementation. A complete
implementation for Pascal will be available by September 30, 1979.
Partially complete implementations which omit segments such as files
and passing of procedures as parameters will be available earlier (early Summer).
The modification to Pascal and the upgrade to provide
a full compiler will require additional support
for the P-code to S-1 translator.
Also, implementation of the P-code to P-code optimizer 
by Richard Sites will require changes to the compilers
in order to support the optimizer. These changes will 
be done as they appear during the
optimizer development.

Lastly, in order to effectively compile multi-module programs,
intermodule type checking must be supported. At the present
time this problem has received only cursory addition. The first
step is to specify a method for accomplishing the type checking.
This will result in a proposed design for the intermodule
type checker by July 1, 1979. The implementation will then proceed,
and reach completion on September 30, 1979.

.ss Operating System Kernel Design

It is proposed to investigate the design of the kernel for the 
S-1 multiprocessing operating system. Since the kernel 
frequently determines the quality of the entire operating system,
especially with respect to performance, security, and reliability,
it deserves special consideration in the design process.
This portion of the proposed work will aim at
specifying a kernel which will support the variety 
of operating system requirements, which arise in the S-1 
environment. Issues such as what the kernel should 
contain and insuring reliability in the kernel will be the
main focus of the work. A preliminary specification
of the kernel functions will be delivered on July 1, 1979.
After interaction with the LLL operating systems group,
final specification and a design for the kernel will be 
worked on. The final specification and a design for the kernel
will be completed by September 30, 1979.


.app New Personnel
.cb Forest Baskett
Forest Baskett has been involved in operating system design and
development since 1962.  He worked with the Rice Computer and developed
parts of the Codeword based operating system for that computer in the
early '60s.

He was one of the principal designers and implementers of one
of the earliest and best time-sharing systems on CDC 6600's, the UT
operating system at the University of Texas.  He was the principal
designer of DEMOS, a modern kernel based, process structured operating
system for the CRAY-1.  He has published numerous papers on computing
system design and development.

.cb John Hennessy
Professor John Hennessy's research interests include programming language
design and implementation, operating systems design, and distributed systems.
In the area of programming language design he has designed a real-time
programming language, providing support for stand-alone systems.  Recently,
under S-1 funding, he has worked on the design of an extension of the
programming language Pascal, to support systems programming on the S-1.
He has also been involved in the design and maintenance of two Pascal compilers.
Currently, he is initiating work on the problems of software portability
and interactive high level language debuggers. 

Professor Hennessy is also conducting research on the topic of
distributed computing and its incorporation into a programming
language.  This research is based on the incorporation of message 
passing and synchronization capabilities into a standard process structure.
The goal is to provide simple tools to support the construction of reliable
distributed software systems.  This is important to the S-1 project, since it 
is reasonable to consider a message passing system within the operating
system, as well as available to the users.
.app Text of December 1977 Proposal
.section←null;
.s Goals

Building on a substantial background in computer timesharing system development
(see Appendix C), the Stanford Artificial Intelligence Laboratory
(SAIL) proposes to participate in the Lawrence Livermore Laboratory (LLL)
program for development of the S-1 computer system by designing certain elements
and developing an efficient operating system over a period of three years.
This proposal covers the first 9 months' work.


The proposed work will have the following subgoals:

1) Design and begin development of an operating sysem for both single and
multiprocessor S-1 computer configurations with dedicated disk systems.
This system will provide efficient resource allocation for configurations
of 1 to 32 processors and will include user interactive facilities that
are optimized for display terminals, though teleprinter terminals will
also be supported.  In addition to the operating system, a number of
utility programs will be developed, including text editors, file
management programs, compilers, and debuggers.

SAIL recognizes that the S-1 Project requires an evolving operating system
for the various computer configurations it is creating, and will undertake
to create an operating system that will have some minimal capability early
in the effort, growing thereafter in capability in frequent increments.

2)  Based on work done in pursuit of the first subgoal, recommend
specific equipment characteristics needed to support efficient
operation.  This particularly includes the manner in which
secondary memories and peripherals will connect to various S-1
system configurations.

3) Support S-1 Project hardware development, in fashions and to extents
mutualy agreed upon by cognizant SAIL and LLL staff.  During the period of
this initial proposal such support activity will include
detailed design of the crossbar switch for the first S-1 multiprocessor
configuration and the post-construction debugging and documentation of
this hardware module.

.s Work Plan
.ss Operating System Development

The operating system to be developed will exploit the full suite of
capabilities of multiprocessor S-1 configurations and will use the better
features of existing timesharing systems, such as Unix, Multics, TOPS-20,
ITS, and the Stanford Monitor.  However, it will also be capable of 
specialization for use with single processor S-1 configurations.  There
will also be some innovation in interactive user services.

A key problem to be solved is efficient allocation and scheduling of
resources.  It should be possible to flexibly allocate processors either
to a number of tasks supporting independent users or to separate forks
of a single task, depending on priorities.

The planning phase of this work (of about three months' duration)
will be devoted to the following tasks:
.bs
(1) familiarization with the S-1 equipment characteristics;

(2) characterization of the principal kinds of computing tasks that are to
be performed with this system;

(3) general design of program services to be provided by the operating
system, including primary memory allocation and file system
characteristics;

(4) general design of user services, including display control, command
languages, and character set standards;

(5) analysis of other resource allocation issues;

(6) study of major existing operating systems to determine which of their
features may be profitably included in the one to be created, and which,
if any, of their major modules may be appropriately carried over into the
new operating system;

(7) formulation of criteria for selection of programming languages to be
used in major development tasks.
.end continue
This phase of the work will culminate with the generation of a
report documenting the results of performing these 7 tasks.

Other products of this phase will include an assortment of planning
documents and specific recommendations on equipment design issues, such
as how the disk storage units should be interfaced to the multiprocessor
system.

The subsequent design phase (of about six months' duration) will focus
on detailed design of the functional elements of the system, selection of
system programming languages, programming of developmental tools (e.g., 
simple editors and debuggers), and possibly the modification of a
compiler to produce S-1 code.

.ss Crossbar Switch Design

It is proposed to design a crossbar switch to connect 16 S-1 processors
with 16 memory modules with a maximum concurrency of 16, and a throughput of
70 nanoseconds per word, as specified in Reference 1.
The switch will contain logic to allow an LSI-11 
processor, connected through an LLL-supplied parallel interface, to perform
comprehensive testing of the switch (both by providing artificial stimuli
to the switch, and by reading the state of switch buses and signals) and to
recover from what are considered to be probable recoverable failure modes of
the switch, processors, and memory modules.

SAIL proposes to perform the following subtasks of this basic task
during the current proposal period:
.bs
1) Familiarization of SAIL design personnel with the S-1 Design System.

2) Complete logical design of the switch using the S-1 Design System
Graphics Language.

3) Complete physical design of the switch, including layout and cable
assignment.

4) Production of final wire-lists through the S-1 Design System.

5) Debugging, including demonstration of full switch functionality, using
the LLL-supplied LSI-11 diagnostic system.

6) Documentation, including a structured text description of the hardware
to augment the structured drawings, and a high-level description of switch
operation.
.end

All aspects of crossbar switch hardware implementation is proposed
to be the responsibility of LLL.  At the completion of Step 4 (above), it
is proposed that LLL will construct the switch, associated cabinetry, and
LSI-11 debug processor, and will thereupon make the switch available for
debugging by SAIL staff.
Throughout the design, cognizant SAIL staff members will maintain
close contact with cognizant LLL staff members.

.s Facilities

Much of the planning and preliminary programming work on both projects
will be performed on the existing computer facilities of the Stanford
Artificial Intelligence Laboratory.  Since this equipment has already been
purchased, mostly with U. S. Government research funds, the only costs
involved in its use will be the support of part of a computer technician
and a share of other maintenance costs.

It is proposed that LLL make available to the Stanford Artificial
Intelligence Laboratory fractions of the capabilities of both single
processor and multiprocessor S-1 configurations appropriate to various
phases of advanced operating systems development and debugging.  Determination
of how this is to be most effectively accomplished is to be made
jointly by cognizant LLL and SAIL personnel, as such needs evolve.  It is
anticipated that some phone line access to LLL-based S-1 hardware
configurations will be needed and a budget item to support such access is
included.

.s Coordination and Reporting

It is proposed that primary coordination between cognizant LLL and SAIL
staff members be accompished via monthly meetings, to be conducted for
approximately half-day periods.  Senior SAIL
Project members will document the salient topics addressed at these 
conferences (including accomplishments of the previous month, and the
relatively detailed work plan for the upcoming month) and distribute such
documents to all cognizant SAIL and LLL staff members as the primary project
coordination papers.

SAIL proposes to submit two interim technical reports to LLL dealing
with the progress made during the Winter and Spring Quarters of 1978, and a
final, comprehensive report which treats in detail all aspects of the work
done during the January-September, 1978, period.  It is anticipated that the
Winter Quarter document will report the results of the 7-point operating
sysem planning phase discussed in Section 2.1, as well as the first three
items of the crossbar switch development discussed in Section 2.2.  It is
likewise expected that the Spring Quarter document will report preliminary
results of the operating system design phase of Section 2.1, and will also
report successful completion of at least 2 of the final 3 items of the switch
development of Section 2.2.  The final report will detail the design of the
operating system of Section 2.1, and will include the description of the
switch design implementation and debugging work of Section 2.2.  All these
reports will be delivered to LLL within 30 days of the end of the periods on
whose results they report.

.app SAIL Background in System Development

While the primary interests of the Stanford Artificial Intelligence
Laboratory have been in artificial intelligence, mathematical
theory of computation, and related theoretical problems, certain members
of the SAIL staff have been involved for many years in the development of
timesharing systems, programming languages, and interactive facilities.
Some of these activities are outlined below.

The concept of a general purpose timesharing system was first proposed by
John McCarthy when he was at MIT [2].  That proposal led to the pioneering
systems developed in Project MAC.  McCarthy also participated in the
development of an early timesharing system at BBN [3].

Shortly after arriving at Stanford in 1962, McCarthy undertook the development
of the first display-oriented timesharing system [4], based on a PDP-1 computer
with 12 displays and a link to an IBM 7090.  One notable accomplishment of
this project was the development of a "page editor" called TVEDIT that
exploited the capabilities of displays in text editing.  This was the forerunner
of screen editors now in use at SAIL and in a number of other advanced timesharing
systems.

When the SAIL computer facility was assembled in 1966, the staff of the PDP-1
timesharing project became the nucleus of the computer system staff that
developed a display-oriented system on a DEC PDP-6 computer initially and
later on KA10 and KL10 processors.
There are currently 70 display terminals connected to the system, most of
them with full graphics capability [5, 6].  There is also a connection to
the Arpanet, permitting remote access to and from hundreds of other
computers around the world.
In addition to providing conventional timesharing services, this system
handles realtime control of mechanical arms and television cameras, in
support of research in automatic mechanical assembly and computer vision [7].

In the period 1970-73, SAIL staff members designed a high speed processor
known as "Super Foonly", which featured a cache memory, user-accessible
microcode, and a "console computer" (a minicomputer that monitors the main
processor).  The latter innovation has since been included in a number of
other machines, including the S-1.
After the design was completed, it was made available to Digital Equipment
Corporation, which used it as the basis for their Decsystem/10 and Decsystem/20
computer systems.
The KL10 processor now at SAIL was donated by DEC out of gratitude for the
design contribution.

Another important outgrowth of this computer design project was a design
automation system known as SUDS [8], which combined interactive drawing
facilities with other computer-aided design services.
This was the first system that permitted a designer, working through a display
terminal, to completely design complex digital devices, including printed
circuit boards and backpanel wiring.
The system automatically produces artwork for PC boards and control tapes for
automatic wiring machines.
SUDS has been used to design five large computers so far, as well as
countless other digital devices.
It is currently in use at MIT, Carnegie-Mellon University, and
Digital Equipment Corporation, among other places, and is the basis of the
S-1 Design System.

Other interests of the SAIL staff include the development of
assemblers [9], the LISP family of programming languages and systems [10, 11, 12],
the SAIL language and compiler [13], text editors [14, 15], interactive
debuggers [16], document compilers [17], and computer communication systems [18].

The backgrounds of the individuals who will carry out the proposed work are
as follows.
John McCarthy, who will provide overall direction of the project,
is a Professor of Computer Science and Director of SAIL.
He has 26 years experience as a faculty
member at a number of major universities and has been a principal innovator
in artificial intelligence, mathematical theory of computation, and timesharing
systems.
Les Earnest, who is Associate Director of SAIL, will handle much of the
management of the project.  He has 24 years experience in programming, computer
system design and technical management.

Jeff Rubin, who will head the operating system design effort, is currently
in charge of system programming at SAIL and has twelve years experience as
a programmer, including six years as a system programmer at MIT and four
years in this capacity at SAIL.
Ted Panofsky, who will design the crossbar switch, is head of the SAIL
Computer Facility group, has been a design engineer at SAIL for ten years,
and had several years of electronics experience before that.
Martin Frost has been a systems programmer at SAIL for five years.

.bib;
⊗  Tom McWilliams and Curt Widdoes, "The S-1 Memory Interface",
October 3, 1977.

⊗  John McCarthy, "A Time Sharing Operator Program for our Projected IBM 709",
memo to P. M. Morse, MIT, January 1, 1959.

⊗  John McCarthy, S. Boilen, E. Fredkin, J.C.R. Licklider, "A Time-sharing
Debugging System for a Small Computer", <Proc. AFIP Conf.> (SJCC), Vol. 23,
1963.

⊗  John McCarthy, D. Brian, G. Feldman, J. Allen, "THOR -- A Display Based
Time-sharing System", <Proc. AFIPS Conf.> (FJCC), Vol. 30, Thompson,
Washington, D.C., 1967.

⊗  Brian Harvey and Martin Frost, "Monitor Command Manual", SAILON-54.5,
January 1976.

⊗  McCarthy, John, Lester Earnest, D. Raj. Reddy, Pierre Vicens, "A
Computer with Hands, Eyes, and Ears", <Proc. AFIPS Conf.> (FJCC),
1968.

⊗  Martin Frost, "UUO Manual", SAILON-55.5, October 1977.

⊗  Richard Helliwell, "Stanford Drawing Program", SAIL Program Note, 1971.

⊗  Fred Wright and Ralph Gorin, "FAIL", AIM-226, April 1974.

⊗  John McCarthy, "Recursive Functions of Symbolic Expressions", <Communications
of the ACM>, April 1960.

⊗  John McCarthy, <et al, LISP 1.5 Programmer's Manual,>, MIT Press, 1962.

⊗  David C. Smith, "MLISP User's Manual", AIM-84, January 1969.

⊗  John Reiser (ed.), "SAIL", AIM-289, August 1976.

⊗  William Weiher and Steve Savitzky, "Son of Stopgap", SAILON-50.3, October 1970.

⊗  Arthur Samuel and Martin Frost, "E Text Editor", Program Note, December 1977.

⊗  Phil Petit, "RAID", SAILON-58.1, February 1970.

⊗  Larry Tesler, "PUB, the Document Compiler", SAILON-70, September 1970.

⊗  John McCarthy and Les Earnest, "DIALNET and the Home Terminal", <Proc.
Computer Faire>, San Francisco, 1977.

.end
.next page; app Budget
.skip; once center
Twelve months beginning 1 January 1979
.begin "bud"
.nofill
.turn on "α∂→\{"; tabs 32;
.			<< put commas in INCR and print it >>
.at "!" incr "∞"	⊂
.  if incr≤0 then sal←"" else sal←incr[∞-2 to ∞]; digs←incr/1000;
.  while("digs>0",|sal←digs[∞-2 to ∞]&","&sal; digs←digs/1000;|);
.  sal;
.  ⊃
.macro subtot	⊂
→_______
. ⊃
.macro percent(num)	⊂(((num+50)/100)&"α%")⊃;
.
.tot←0;		<< total costs >>
.
.		<< salary = semi*man_months*inflation_factor >>
.at "@" semi "," mo "." frac "∞"	⊂
. annual←(semi*(mo*10+frac)*1023+2500)/5000;	tot←tot+annual;
→mo.frac\ →!annual∞
. ⊃
.at "#" amt "∞"	⊂ val←amt; tot←tot+val;
→!val∞
.  ⊃

→%3Person\
→Months\
%3A. Salaries and Wages%1

   1. Senior Personnel:

      a. John McCarthy @1806,0.8∞
	 Prof. of Computer Science
	 5α% acad. yr., 10α% summer

      b. Forest Baskett @1278,3.4∞
	 Assoc. Prof. of C.S. & E.E.
	 25α% acad. yr., 40α% sum.

      c. Lester Earnest @1632,1.2∞
	 Senior Research Associate
	 10α%

   2. Other Personnel (full time except
      where specified otherwise):

      a. John Hennessey @972,3.0∞
	 Asst. Prof. of E.E.
	 20α% acad. yr., 40α% sum.

      b. Arthur Samuel @1500,6.0∞
	 Adjunct Prof. of C.S.
	 50α%

      c. Martin Frost @800,4.0∞
	 Systems Programmer
         25α%

      d. Mark Lebrun @750,12.0∞
	 Systems Programmer

      e. Armando Rodriguez @666,12.0∞
         Systems Programmer

      f. Hilding Elmquist @600,3.0∞
	 Systems Programmer, 25α%

      g. Student Res. Assist. @506,7.5∞
	 50α% acad. yr., 100α% sum.

      h. Support Personnel:

	 (1) Secretary (75α%) @480,9.0∞

	 (2) Elect. Tech. (25α%) @684,3.0∞
.subtot
      Total Salaries & Wages →!tot∞

%3B. Staff Benefits%1 #(tot*2020+5000)/10000∞
     19.5α% till 1 Sept.'79,
     21.6α% thereafter

%3C. Travel%1 (domestic) #7500∞

%3D. Other direct costs %1 #22700∞
     (e.g. telephone, publications,
     office supplies, copying,
     postage, computer repair services)

%3E. Indirect Costs%1 #(tot*58 +50)/100∞
     (58α% of A thru D)

%3F. Permanent Equipment%1 #7200∞
     3 Datamedia display terminals

.subtot
.tty←"Total="&tot;
%3G. Total Costs →!tot∞

.end "bud"